package com.jia.jianzhiOffer;

/**
 * 剑指 Offer 47. 礼物的最大价值
 */
public class Pro47 {
    public int maxValue(int[][] grid) {
        for(int r = 0; r < grid.length; r++) {
            for(int c = 0; c < grid[0].length; c++) {
                if(r == 0 && c == 0) {
                    continue;
                }else if(r == 0) {
                    grid[r][c] += grid[r][c-1];
                }else if(c == 0) {
                    grid[r][c] += grid[r-1][c];
                }else {
                    grid[r][c] += Math.max(grid[r-1][c], grid[r][c-1]);
                }
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}
